#include <bits/stdc++.h>
using namespace std;
int n, m, p[10], ans = 666;
bool G[10][10], vis[10], T[10][10];
void dfs(int k) {
    // 生成排列的第 k 位
    if (k > n) { // 生成结束了
        int res = 0;
        memset(T, false, sizeof(T));
        for (int i = 1; i <= n; i++) T[i][p[i]] = T[p[i]][i] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                res += T[i][j] ^ G[i][j];
            }
        }
        ans = min(ans, res);
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && k != i && (i >= k || p[i] != k)) {
            vis[i] = true;
            p[k] = i;
            dfs(k + 1);
            vis[i] = false; // 回溯
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u][v] = G[v][u] = true; // 邻接表
    }
    dfs(1);
    printf("%d\n", ans);
    return 0;
}